﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;
//#include<stdio.h>
//int main()
//{
//	double squre = 0;
//	scanf("%lf", &squre);
//	squre *= 0.75;
//	printf("%.6lf", squre);
//	return 0;
//}

//#include<vector>
//int main()
//{
//	vector<int> ret;
//	int T = 0;
//	cin >> T;
//	while (T--)
//	{
//		int Pnum = 0;
//		cin >> Pnum;
//		int count = Pnum;
//		vector<int> fuwuqi;
//		int tmp = 0;
//		while (count--)
//		{
//			cin >> tmp;
//			fuwuqi.push_back(tmp);
//		}
//		count = Pnum;
//		vector<int> jineng12;
//		vector<int> jineng34;
//		for(int i=0;i<count;i++)
//		{
//			cin >> tmp;
//			if (fuwuqi[i]==1 || fuwuqi[i]==2)
//			{
//				jineng12.push_back(tmp);
//			}
//			if (fuwuqi[i] == 3 || fuwuqi[i] == 4)
//			{
//				jineng34.push_back(tmp);
//			}
//		}
//		int max12 = 0, max34 = 0, min12 = INT_MAX, min34 = INT_MAX;
//		for (auto e : jineng12)
//		{
//			if (e > max12)
//			{
//				max12 = e;
//			}
//		}
//		for (auto e : jineng12)
//		{
//			if (e < min12)
//			{
//				min12 = e;
//			}
//		}
//		for (auto e : jineng34)
//		{
//			if (e > max34)
//			{
//				max34 = e;
//			}
//		}
//		for (auto e : jineng34)
//		{
//			if (e < min34)
//			{
//				min34 = e;
//			}
//		}
//		int ret1 = max34 - min12;
//		int ret2 = max12 - min34;
//		
//		if (ret1 > ret2)
//		{
//			ret.push_back(ret1);
//		}
//		else
//		{
//			ret.push_back(ret2);
//		}
//		jineng12.clear();
//		jineng34.clear();
//		fuwuqi.clear();
//	}
//	for (auto e : ret)
//	{
//		cout << e << endl;
//	}
//	return 0;
//}

//#include<vector>
//int main()
//{
//	vector<int> ret;
//	int t = 0;
//	cin >> t;
//	while (t--)
//	{
//		vector<int> B;
//		int num = 0;
//		cin >> num;
//		int count = num;
//		while (count--)
//		{
//			int tmp = 0;
//			cin >> tmp;
//			B.push_back(tmp);
//		}
//		count = num;
//		vector<int> x;
//		while (count--)
//		{
//			int tmp = 0;
//			cin >> tmp;
//			x.push_back(tmp);
//		}
//		for (int i = 0; i < num; i++)
//		{
//			int max = -1;
//
//			for (int j = 0; j <= i; j++)
//			{
//				if (B[j] <= x[i] && max < B[j] )
//				{
//					max = B[j];
//				}
//			}
//			if (max <= x[i])
//			{
//				ret.push_back(max);
//			}
//			else
//			{
//				ret.push_back(-1);
//			}
//			
//		}
//	}
//	for (auto e : ret)
//	{
//		cout << e << endl;
//	}
//	return 0;
//}
// 
// 
//#include<iostream>
//using namespace std;
//
//int main()
//{
//	long long n = 0;
//	cin >> n;
//	long long sum = 0;
//	for (long long i = 1; i <= n; i++)
//	{
//		sum += i;
//	}
//	long long avg = sum / n;
//	cout << sum << endl;
//	cout << avg << endl;
//	return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//
//int main()
//{
//	int t = 0;
//	cin >> t;
//	vector<int> ret;
//	while (t--)
//	{
//		int size = 0;
//		cin >> size;
//		string s;
//		cin >> s;
//		int qnum;
//		cin >> qnum;
//		while (qnum--)
//		{
//			char x;
//			char y;
//			int l;
//			cin >> x >> y >> l;
//			int left = 0;
//			int right = left + l-1;
//			int sum = 0;
//			while (right < size)
//			{
//				if (right < size && s[right] == x || s[right] == y)
//				{
//					sum++;
//				}
//				left++; right++;
//			}
//			ret.push_back(sum);
//		}
//	}
//	return 0;
//}


